package com.xigua._回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: ${todo}
 * @date 2022/2/1020:10
 */
public class _40_组合总和II {

    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.print(integer+" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates,result,target,new ArrayList<Integer>(),0,0);
        return result;
    }

    private static void dfs(int[] candidates, List<List<Integer>> result, int target, ArrayList<Integer> nums, int sum, int index) {
        if (sum == target){
            result.add(new ArrayList<>(nums));
            return;
        }
        for (int i =index; i < candidates.length; i++) {
            if (i > index && candidates[i] == candidates[i-1]) continue;
            int res = sum +candidates[i];
            if (target >= res ){
                nums.add(candidates[i]);
                dfs(candidates,result,target,nums,res,i+1);
                nums.remove(nums.size()-1);
            }else {
                break;
            }
        }

    }


}
